/**
 * @param {number} c
 * @return {boolean}
 */
export var judgeSquareSum = function (c) {
  let left = 0
  let right = Math.floor(Math.sqrt(c))
  while (left <= right) {
    const sum = left * left + right * right
    if (sum === c) {
      return true
    } else if (sum < c) {
      left++
    } else {
      right--
    }
  }
  return false
}

/**
  费马平方和定理：
  一个非负整数 cc 如果能够表示为两个整数的平方和，当且仅当 c 的所有形如 4k + 3 的质因子的幂均为偶数。
 * @param {number} c
 * @return {boolean}
 */
export var judgeSquareSum2 = function (c) {
  for (let base = 2; base * base <= c; base++) {
    // 如果不是因子，枚举下一个
    if (c % base !== 0) {
      continue
    }

    // 计算 base 的幂
    let exp = 0
    while (c % base == 0) {
      c /= base
      exp++
    }

    // 根据 Sum of two squares theorem 验证
    if (base % 4 === 3 && exp % 2 !== 0) {
      return false
    }
  }

  // 例如 11 这样的用例，由于上面的 for 循环里 base * base <= c ，base == 11 的时候不会进入循环体
  // 因此在退出循环以后需要再做一次判断
  return c % 4 !== 3
}
